/// @tags: DuJiaoSieve
#include <cstdio>
#include <iostream>
#include <unordered_map>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

typedef long long LL;

constexpr int maxn = 5e6;

int pcnt;
int pri[maxn];
bool vis[maxn];
LL mul[maxn], phi[maxn];
std::unordered_map<int, LL> sumMu, sumPhi;

LL getSumMu(int n) {
  if (n < maxn) return mul[n];
  if (sumMu.find(n) != sumMu.end()) return sumMu[n];
  LL res = 1;
  for (LL l = 2, r = 0; l <= n; l = r + 1) {
    r = n / (n / l);
    res -= (r - l + 1) * getSumMu(n / l);
  }
  return sumMu[n] = res;
}

LL getSumPhi(int n) {
  if (n < maxn) return phi[n];
  if (sumPhi.find(n) != sumPhi.end()) return sumPhi[n];
  LL res = n * ((LL)n + 1) / 2;
  for (LL l = 2, r = 0; l <= n; l = r + 1) {
    r = n / (n / l);
    res -= (r - l + 1) * getSumPhi(n / l);
  }
  return sumPhi[n] = res;
}

inline int main() {
  phi[1] = mul[1] = 1;
  for (rint i = 2; i < maxn; ++i) {
    if (!vis[i]) {
      pri[++pcnt] = i;
      mul[i] = -1, phi[i] = i - 1;
    }
    for (rint j = 1; j <= pcnt && pri[j] * i < maxn; ++j) {
      vis[i * pri[j]] = true;
      if (i % pri[j] == 0) {
        phi[i * pri[j]] = phi[i] * pri[j];
        break;
      } else {
        mul[i * pri[j]] = -mul[i];
        phi[i * pri[j]] = phi[i] * phi[pri[j]];
      }
    }
  }
  for (rint i = 1; i < maxn; ++i) {
    mul[i] += mul[i - 1], phi[i] += phi[i - 1];
  }
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    cout << getSumPhi(n) << ' ' << getSumMu(n) << '\n';
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("CppTest.in", "r", stdin);
  freopen("CppTest.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
